// -*- coding: utf-8 -*- 
/**
 * Project: AlgorithmsLearn
 *
 * @author: yanking
 * Create time: 2022-03-14 00:51
 * IDE: IntelliJ IDEA
 * Introduction:
 */
package com.LeetCodeT.DynamicPlan;

import org.junit.jupiter.api.Test;

import java.util.*;

public class UniquePaths {
    /**
     * 机器人寻路方案
     */
    int ans = 0;
    Map<String, Boolean> point = new HashMap<>();

    public int uniquePathsT(int m, int n) {
        /*
            1 机器人每一步的行走只有两个方向 向右 + 向下
            2 机器人的起点和终点是已知的，当前的状态（位置）也是已知的
            3 可以根据机器人当前的状态判断下一步的行动
         */
        // 当前状态初始化为起点(0,0)
        // HashMap记忆化搜索可以减少时间复杂度
        toTerminal(1, 1, m, n);
        return ans;
    }

    private void toTerminal(int x, int y, int m, int n) {
        if (x == m && y == n) {
            ++ans;
            return;
        }
        if (point.containsKey(x + "" + y)) {
            // 记忆化搜索
            ++ans;
            return;
        } else {
            point.put(x + "" + y, true);
        }
        if (x < m) {
            toTerminal(x + 1, y, m, n);
        }
        if (y < n) {
            toTerminal(x, y + 1, m, n);
        }
    }


    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 中间存在障碍物
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int m = obstacleGrid.length, n = obstacleGrid[0].length;
        int[][] dp = new int[m][n];
        for (int i = 0; i < n; i++) {
            //初始化第一行为1
            if (obstacleGrid[0][i] == 0) {
                dp[0][i] = 1;
            } else {
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            //初始化第一列为1
            if (obstacleGrid[i][0] == 0) {
                dp[i][0] = 1;
            } else {
                break;
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (obstacleGrid[i][j] == 0) {
                    dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
                } else {
                    dp[i][j] = 0;
                }
            }
        }
        return dp[m - 1][n - 1];
    }

    @Test
    public void shout() {
        int m = 3, n = 7;
        //System.out.println(uniquePaths(m, n));
    }


//    public int uniquePathsT(int m, int n) {
//        /*
//            改进方案，将递归方法改为迭代+回溯
//         */
//        Stack<int[]> stack = new Stack<>();
//        stack.push(new int[]{1, 1});
//        while (!stack.isEmpty()) {
//            int[] top = stack.pop();
//            if (top[0] < m) {
//                stack.push(new int[]{top[0], top[1]});
//            }
//
//        }
//        return ans;
//    }
}
